模拟赛题解/2025.9.16 模拟赛

T1-王哥与荷塘（fish）

题面

荷塘是一个平面直角坐标系，其中有 $n$ 条鱼，编号为 $1,2,\cdots,n$，位置用一个点 $(x_i,y_i)$ 表示（可以重复）。它们听路过的王哥提到 “平面最远点对”，于是想亲身实践一下——进行 $m$ 次操作，每次为以下两种之一：

• 充分发扬鱼类智慧，将编号在 $[l,r]$ 中的鱼的位置绕原点逆时针旋转 。
• 询问编号在 $[l,r]$ 中的鱼两两之间（包括自己和自己）的最大曼哈顿距离，即：

$$\max_{l\leq i\leq j\leq r}{|x_i-x_j|+|y_i-y_j|}$$

由于鱼的记忆只有七秒，难以进行大量的运算，所以它们想请你帮忙给出答案。

$1\leq n,m\leq2\times10^5,1\leq x_i,y_i\leq10^8,1\leq l\leq r\leq n$。

题解

首先考虑将曼哈顿距离转化为切比雪夫距离，此时只需要维护 $x,y$ 分别的 $\max/\min$。

注意到每次操作实质上是使 $x'\leftarrow y,y'\leftarrow -x$。

因此只需要用线段树维护 $tag=1/2/3/4$，表示旋转次数，维护区间最大/最小 $x/y$。

T2-王哥与演出（oblivious）

题面

王哥将要带领乐队成员在一个 $r$ 行 $c$ 列的舞台上演出。为了增加节目效果，她决定在 $n$ 个装饰品中选择一些来装饰舞台。根据讨论，她们确定了每个装饰品在舞台上的预设位置 $(x_i,y_i)$ 和记忆值 $a_i$。她将通过两轮选择来确定这次演出最终的装饰品：

• 第一轮，在每一行中至多选择一个装饰品。
• 第二轮，在每一列中至多选择一个装饰品。

注意，两轮有先后顺序，并且要求第一轮选择的物品在第二轮中不能再被选择。

定义一场演出的记忆值为选择的所有装饰品记忆值之和。王哥希望乐队成员和观众都能记住这场演出，于是请你帮助她最大化这场演出的记忆值。

$1\leq n,r,c\leq10^6,1\leq x_i\leq r,1\leq y_i\leq c,1\leq a_i\leq 10^9$。

题解

考虑图论建模。把每一行、每一列都视作一个点，把饰品视为边，我们会得到一个 $r+c$ 个点，$n$ 条边的图。若有一张第 $u$ 行第 $v$ 列的饰品 $a_i$，那么就视作一条连接 $u$ 和 $v+r$，边权为 $a_i$ 的边。

用选择饰品的的过程将边定向。在第一轮中，在第 $u$ 行取走第 $v$ 列的饰品，就将边定向为 $u\rightarrow v+r$；在第二轮中，在第 $v$ 列取走第 $u$ 行的饰品，就将边定向为 $v+r\rightarrow u$。

对于一种合法的选择方式，考察定向后的建出的新图的性质。容易发现一个结点的出度不超过 $1$，那么整个新图就是若干棵树与内向基环树的组合。最后将边转为无向。

要求权值最大化，就是对每个连通块求出最大生成树，或者最大生成基环树。可以仿照 Kruskal 算法贪心地取边，与一般的 MST 相比只需要额外判环。

时间复杂度 $O(n\log n)$。

T3-王哥与序列（array）

题面

有一个长为 $n$ 的序列 $a$，王哥认为一个序列是优美的，当且仅当序列中所有数都相同。但是序列 $a$ 初始时很有可能不是优美的，所以王哥想让其变得优美。

定义一次操作为：选择三个整数 $(l,r,x)$ 满足 $1\leq l\leq r\leq n$，将区间 $[l,r]$ 内的所有 $a_i$ 都加上 $x$（$x$ 可以为负数）。

王哥想问你，最少用多少次操作，可以使序列变得优美。然而王哥认为这太简单了，所以他还想知道，在最小化操作次数的前提下，有多少种不同的操作方案能使得序列变得优美。

两种方案不同，当且仅当存在一个 $i$ 使得两种方案第 $i$ 次操作的三元组 $(l,r,x)$ 不同。特别地，不进行操作也可以算一种方案。答案对 $10^9+7$ 取模。

当然，如果你只知道第一问的答案，王哥也会给你一部分分数。

$1\leq n\leq22,|a_i|\leq 10^{12}$。

题解

设差分数组 $d_i = a_{i+1} - a_i$，转化为在 $d_1 \dots d_{n-1}$ 上考虑。每次可以选择 $(x, v)$ 让 $d_x$ 加上 $v$，或者选择 $(x, y, v)$ 让 $d_x$ 加上 $v$，$d_y$ 减去 $v$。

考虑图论建模，如果一次操作选择了 $(x, v)$，就是连 $x$ 的自环，如果是 $(x, y, v)$，就是 $x, y$ 的无向边。可以发现，在最优策略下，对于一个大小为 $k$ 的连通块：

• 如果这个连通块中的 $d_i$ 都为 $0$，那么一定会连 $k-1$ 条边，即形成一棵树；

• 否则一定会连 $k$ 条边，即一棵树加上一个自环，相当于先操作一个数让连通块的和为 $0$，然后变成上面的情况。

那么求最小的操作次数，相当于将 $\{d_1, d_2, \dots, d_{n-1}\}$ 划分为几个不交的集合，最大化集合内元素和为 $0$ 的集合数量 $c$，答案就是 $n-1-c$。于是可以子集 $\text{dp}$，设 $f_S$ 表示集合 $S$ 最多划分为多少个元素和为 $0$ 的集合，复杂度为 $O(3^n)$。

接下来考虑如何求方案数，设第一问答案为 $c$，我们求出不同的操作集合有多少种可能，最后乘上 $c!$。对于一种最小操作次数的集合划分方案，考虑每个集合 $S$，如果 $\sum_{x \in S} d_x = 0$，那么可以发现每一棵树树对应了一种方案。具体地，对于一棵树，我们可以任选定根一个根，然后对于所有连接叶子节点的边动过几次确定操作的权值是什么，进而可以依次往上确定每个操作的权值是什么。所以方案数为 $|S|^{|S|-2}$。

对于 $\sum_{x \in S} d_x \neq 0$ 的集合，我们将这些集合一起考虑。而对于一个自环，可以看作是和 $0$ 之间连边。于是我们可以把 $0, n$ 这两个点当成一个连通块，那么一个方案可以看作是集合 $S$ 和 $0, n$ 连通块的成的一棵树，根据 prufer 序列，方案数为 $2(|S|+2)^{|S|-1}$。设 $g_S$ 表示在最大化元素和为 $0$ 的集合数时，有多少种划分方案。于是第二问也可以 $O(3^n)$ 回答。

接下来考虑第三问，对于第一问，事实上我们不用枚举子集，只需要转移 $f_S = \max_{i \in S} f_{S \setminus i} + [\sum_{x \in S} d_x = 0]$ 即可。但如果这样转移会有一个空集重置，于是我们记录一个 $g_{S,j}$ 表示集合 $S$，和不为 $0$ 的集合大小为 $j$，元素和不为 $0$ 的子树经过的。当 $S$ 元素和为 $0$ 时，我们只用 $j$ 去掉集合中最小元素标号的集合来更新；然后对于所有 $j$，会被算重 $(j-1)! \cdot V$ 次，所以要 $g_{S,0} \gets g_{S,0} - \sum_j (j-1)! \cdot g_{S,j}$。

时间复杂度为 $O(2^n n^2)$。

T4-王哥与数字（digit）

题面

王哥认为如果一个数从高到低位的数字是单调不增的，那么这个数是有趣的。例如 $977431$ 就是有趣的，而 $114514$ 就不是有趣的。

王哥很快想到了一个问题，求一个区间 $[L,R]$ 内有多少个数是有趣的，但是他觉得这实在是太简单了。于是王哥加强了一下这道题：

给定区间 $[L,R]$ 和一个正整数 $k$，有 $k$ 个变量 $a_1,a_2,\cdots,c_k$，每个变量为整数且在 $[L,R]$ 之间。求在 $(R-L+1)^k$ 种不同的变量取值方案中，有多少种取值方案 $a_1,a_2,\cdots,a_k$，满足 $\sum_{i=1}^ka_i$ 是有趣的。

两种方案不同当且仅当存在一个 $i$ 使得 $a_i$ 在两种方案中的取值不一样。答案对 $998244353$ 取模。

$1\leq L\leq R\leq10^{1000},1\leq k\leq50$。

题解

设 $s$ 是一个有趣的数，考虑求 $s$ 的贡献是多少，即有多少种取值方案满足 $\sum_{i=1}^k a_i = s$。先将问题转化为 $k$ 个范围为 $[1, R-L+1]$ 内的变量加起来为 $s-k(L-1)$。考虑容斥，钦定有 $i$ 个变量取值 $> R-L+1$，问题变为 $k$ 个正整数加起来为 $s-k(L-1)-i(R-L+1)$，用插板法可得答案为

$$\binom{s-k(L-1)-i(R-L+1)-1}{k-1},$$

所以贡献为：

$$\sum_{i=0}^k (-1)^i \binom{k}{i} \binom{s-k(L-1)-i(R-L+1)-1}{k-1}.$$

对于每个 $i$ 分别计算答案，那么设 $x = k(L-1)+i(R-L+1)+1$，考虑把原式写成关于 $s$ 的多项式，即：

$$\sum_{s \geq x} \binom{s-x}{k-1} = \frac{1}{(k-1)!}\sum_{s \geq x} (s-x)^{k-1}.$$

于是

$$= \sum_{i=0}^{k-1} (-1)^{k-1-i} \binom{k-1}{i} \Bigg(\sum_{s \geq x} s^i\Bigg)(-x)^{k-1-i}.$$

再展开：

$$= \sum_{i=0}^{k-1} (-1)^{k-1-i} \binom{k-1}{i} \sum_{j=0}^i \binom{i}{j} \Bigg(\sum_{s \geq x} s^j\Bigg)(-x)^{i-j}.$$

现在要对于每个 $j$ 求 $\sum_{s \geq x} s^j$，考虑数位 DP。

设 $f_{i,j,d,0/1}$ 表示考虑了前 $i$ 位，最后一位为 $d$，是否顶着下界，所有有趣的 $s$ 的 $\Big(\sum s\Big)^j$ 是多少。

那么转移相当于求 $(\sum 10s+d)^j$，一项式展开后用 $f_{i-1}$ 的 $j'$ 次方和乘一个系数来转移即可。

设 $\log_{10} R = n$，则复杂度为 $O(10^2 k^3 n)$，常数小可以通过。